package cn.javadog.algorithm.e1_100;

/**
 * 实现 strStr()
 * https://leetcode-cn.com/problems/implement-strstr/
 * @author Sprite
 */
public class Algorithm28 {
	public static void main(String[] args) {
		System.out.println(strStr("mississippi","a"));
	}

	public static int strStr(String haystack, String needle) {
		if (needle.length() == 0) return 0;

		char[] source = haystack.toCharArray();
		char[] target = needle.toCharArray();

		char first = target[0];
		int max = source.length-target.length;

		for (int i = 0; i <= max; i++) {

			while (source[i] != first && ++i <= max);

			if (i <= max){
				int j = 1;
				int end = target.length-1;
				for (int k = i+1; j<=end && source[k]==target[j]; k++,j++);

				if (j == end+1){
					return i;
				}
			}
		}
		return -1;
	}
}
